| 翻訳と辞書 |
| topological graph theory ： ウィキペディア英語版 |
topological graph theory
In mathematics topological graph theory is a branch of graph theory. It studies the embedding of graphs in surfaces, spatial embeddings of graphs, and graphs as topological spaces.〔J.L. Gross and T.W. Tucker, Topological graph theory, Wiley Interscience, 1987〕 It also studies immersions of graphs.
Embedding a graph in a surface means that we want to draw the graph on a surface, a sphere for example, without two edges intersecting. A basic embedding problem often presented as a mathematical puzzle is the three-cottage problem. More important applications can be found in printing electronic circuits where the aim is to print (embed) a circuit (the graph) on a circuit board (the surface) without two connections crossing each other and resulting in a short circuit.
== Graphs as topological spaces ==
An undirected graph can be viewed as an abstract simplicial complex ''C'' with a single-element set per vertex and a two-element set per edge.〔(Graph topology ), from PlanetMath.〕 The geometric realization |''C''| of the complex consists of a copy of the unit interval () per edge, with the endpoints of these intervals glued together at vertices. In this view, embeddings of graphs into a surface or as subdivisions of other graphs are both instances of topological embedding, homeomorphism of graphs is just the specialization of topological homeomorphism, the notion of a connected graph coincides with topological connectedness, and a connected graph is a tree if and only if its fundamental group is trivial.
Other simplicial complexes associated with graphs include the Whitney complex or ''clique complex'', with a set per clique of the graph, and the ''matching complex'', with a set per matching of the graph (equivalently, the clique complex of the complement of the line graph). The matching complex of a complete bipartite graph is called a ''chessboard complex'', as it can be also described as the complex of sets of nonattacking rooks on a chessboard.
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「topological graph theory」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|